1. Technical Field of the Invention
The present invention relates to multi-stage interconnection networks and, in particular, to a switch with parallel path seeking functionality for use in providing flash-flooding operations in the multi-stage network.
2. Description of the Prior Art
In the field of parallel processing the need for better performing interconnection networks comprising multiple stages is becoming of prime importance. One commonly used switch in multi-stage interconnection networks comprises the asynchronous, low latency, internode switch (or "ALLNODE Switch") which is the subject of several prior pending applications for patent including U.S. application Ser. No. 07/677,543 now abandoned. This switch is operable in two functional switching modes based on the presence of different types of traffic patterns on the network. The first functional mode causes path connections in the network to be broken if "cold" or random traffic encounters blockage in the network. Path establishment through the network is thereafter blindly and successively retried over a different (alternate) path until a connection is made. The second functional mode causes traffic which has been classified as "hot" traffic to camp-on to the switch and not break the path connection to that switch through the network. In accordance with the camp-on functional mode, requests for path connections are placed into a priority queue at the switch where blockage is being experienced. The queued requests are thereafter serviced in order of receipt when the blockage dissipates to make path-connections for the camped-on hot traffic.
There are known disadvantages to the use of the prior art multi-mode All Node Switch as a switch in a multi-stage network. As mentioned above, alternate paths are chosen randomly and blindly by the nodes and their network adapters before entering the network. This approach leads to choosing a fixed path to be tried, with no investigation made prior to selection and try as to whether the chosen path is available. If the fixed path is blocked for random traffic, the network adapter blindly picks an alternate path and tries again to establish a connection. This procedure of random path retrying without advance testing for path availability continues inefficiently (perhaps over several tries without success) until a connection is made.
Accordingly, there is a need for a switch for use in a multi-stage network that utilizes something other than the prior art blind method for finding a connection path through the network. Preferably such an improved switch would search the plural potential paths in parallel while simultaneously identifying the available path or paths for making the connection through the network.